package com.agile.leetcode.node;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author ChenZhangKun
 * @Date 2020/5/27 13:51
 */

/**
 * 返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
 *
 * (回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）
 *
 *
 *
 * 示例：
 *
 * 输入：[8,5,1,7,10,12]
 * 输出：[8,5,10,1,7,null,12]
 *          8
 *         / \
 *        5   10
 *       /\     \
 *      1  7     12
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class PreTranverse {
    public static void main(String[] args) {
        Node node1=new Node(1,null,null);
        Node node7=new Node(7,null,null);
        Node node5=new Node(5,node1,node7);
        Node node12=new Node(12,null,null);
        Node nodeNull=new Node(null,null,null);
        Node node10=new Node(10,nodeNull,node12);
        Node node8=new Node(8,node5,node10);

        preTranverse(node8);
    }

    /**
     * 层次遍历
     * @param node
     */
    public static void preTranverse(Node node){
        if (node!=null){
            Queue<Node> deque=new LinkedList();
            deque.add(node);
            while (deque.size()>0){
                int len=deque.size();
                for (int i = 0; i <len ; i++) {
                    Node poll = deque.poll();
                    if (poll!=null){
                        System.out.println(poll.data);
                    }else {
                        System.out.println("null");
                    }
                    if (poll.leftNode!=null) deque.add(poll.leftNode);
                    if (poll.rightNode!=null) deque.add(poll.rightNode);
                }
            }
        }
    }
}
